import java.util.*;
import java.util.Map.*;
import org.omg.CORBA.INTERNAL;

public class genumHash {
    int d = 10000;
    int k = 20;
    HashMap<String, int[]> genum = new HashMap<String, int[]>();

    public int hash(String input){
        return Math.abs(input.hashCode() % d);
    }

    public void addGenum(String name, String data){
        if(!name.equals("")) {
            genum.put(name, getProfile(data));
        }
    }

    public int[] getProfile(String input){
        int[] p = new int[d];
        for(int i= 0; i<(input.length()-k);i++)
        {
            p[hash(input.substring(i, k+i))]++;
        }
        return p;
    }
    
    /**
     * Compare two profiles
     * @param a
     * @param b
     * @return a double between 0 and 1 that describes similarities.
     */
    public static double compareProfiles(int[] a, int[] b){
    	return (1+angle(a,b))/2;
    }
    
    /**
     * Calculate the angle between 2 vectors
     * @param a
     * @param b
     * @return the angle of the 2 vectors
     */
    private static double angle(int[] a, int[] b) {
    	
    	double angle = dotproduct(a, b) / (length(a)*length(b));
    	
    	return angle;
    }
    
    
    /**
     * Calculate the length of a vector
     * @param a
     * @return the length
     */
    private static double length(int[] a) {
    	
        double length = 0.0;
        for (int i = 0; i < a.length; i++) {
            length += a[i]*a[i];
        }
        length = Math.sqrt(length);
        return length;
    }
    
    /**
     * Calculate the dotProduct of a vector
     * @param a
     * @param b
     * @return the dotProduct
     */
    private static double dotproduct(int[] a, int[] b) {
    	
    	//Check at arrays er lige lange
    	assert a.length == b.length;
    	
        double dotProduct = 0.0;
        for (int i = 0; i < a.length; i++) {
            dotProduct += a[i] * b[i];
        }
        return dotProduct;
    }
    

    public void compareGenum(){
        StdOut.println("### RESULTS ###");
        Iterator<Entry<String,int[]>> it1 = genum.entrySet().iterator();
        String leastAlike = "";
        double least = 1.0;
        String mostAlike = "";
        double most = 0.0;
        while(it1.hasNext()){
            Entry<String, int[]> entry1 = it1.next();
            Iterator<Entry<String,int[]>> it2 = genum.entrySet().iterator();
            while(it2.hasNext()){
                Entry<String, int[]> entry2 = it2.next();
                double similarity = compareProfiles(entry1.getValue(),entry2.getValue());
                StdOut.println(entry1.getKey()+" : "+entry2.getKey()+" = "+similarity);
                if(similarity < least){
                    least = similarity;
                    leastAlike = "LEAST ALIKE: "+entry1.getKey()+" : "+entry2.getKey()+" = "+similarity;
                }
                if(similarity > most && !entry1.getKey().equals(entry2.getKey())){
                    most = similarity;
                    mostAlike = "MOST ALIKE: "+entry1.getKey()+" : "+entry2.getKey()+" = "+similarity;
                }
            }
            System.out.println(mostAlike);
            System.out.println(leastAlike);
        }
    }

    public static void main(String[] args){

        genumHash g = new genumHash();
        String name = "";
        String data = "";

        while(!StdIn.isEmpty()){
            char first = StdIn.readChar();
            if(first=='#'){
                g.addGenum(name, data);
                break;
            }else if(first=='>'){
                g.addGenum(name, data);
                name = StdIn.readLine();
                data = "";
            }else{
                data += StdIn.readLine();
            }
        }
        g.compareGenum();
    }
}
